/*
* 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。(非递归利用栈)
* */
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class inorderTraversalNotDiGui {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        TreeNode node=root;
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            ret.add(node.val);
            node=node.right;
        }
        return ret;
    }
}